【题解】 [USACO4.4]Pollutant Control 网络流 luoguP1344 | Qiuly's blog!

【题解】 [USACO4.4]Pollutant Control 网络流 luoguP1344

Posted on | Edited on | In | Comments:

有必要么……直接打个电话给零售商：”我的牛奶不对，不要收牛奶！”不久可以了吗……

(好了好了这是扯淡)

显然这个运输图的 $1$ 号点就是公司发送牛奶的地方，$n$ 号点就是零售商，然后每一条边就是这个货车的出发点与到达点，边权即为拦截这个货车的代价。

然后呢？

最小的损失……使 $1$ 到不了 $n$ ，这显然就是最小割啊 $QwQ$

那么这样损失数就很容易得到了，那么最少要停的卡车数怎么求呢？很显然，我们任然跑最小割，那么这个图我们将所有边都设为 $1$ ，显然现在的最小割就是最少要停的卡车数。

很显然，时间爆炸，满屏惊喜！

这里有一种方法！我们设一个常数 $T$ ，假设当前边的边权是 $w$ ，那么我们实际连一条边权为 $w \times T+1$ 的边，其中最小损失数显然为 $maxflow/T$ ，那么最少要停的卡车数呢？显然就是 $maxflow\ \%\ T$。

这里的 $T$ 要足够大，否则如果每条边后面的 $+1$ 乘上割的边数大于了 $T$ ，然后 $\%$ 一下，恭喜你！你 $GG$ 了。实际上 “足够大” 只要大于边数就好了，显然这样子建边是要开 $long long$ 的，否则会炸。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<cmath>
#include<queue>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>

#define A printf("A")
#define ll long long
#define RI register int
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))

const ll N=1e5+5;
const ll inf=1e9+9;
const ll T=2019;//2019新年快乐(尽管现在不是时候了)

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

std::queue<int> q;
struct Edge{ll nxt,to,val;}G[N];
ll n,m,s,t,cnt(1),dep[N],head[N];

inline void add(ll u,ll v,ll w){
    G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
    G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt; 
}

inline bool bfs(){
    memset(dep,0,sizeof(dep)); 
    q.push(s);dep[s]=1;
    while(!q.empty()){
        ll x=q.front();q.pop();
        for(ll i=head[x];i;i=G[i].nxt){
            ll y=G[i].to;
            if(dep[y]||G[i].val<=0)continue;
            dep[y]=dep[x]+1,q.push(y);
        } 
    }return dep[t];
} 
inline ll dfs(ll x,ll flow){
    if(x==t||!flow)return flow;
    ll used=0,rlow;
    for(ll i=head[x];i;i=G[i].nxt){
        ll y=G[i].to;
        if(dep[y]==dep[x]+1&&G[i].val){
            used+=(rlow=dfs(y,min(G[i].val,flow-used)));
            G[i].val-=rlow,G[i^1].val+=rlow;
        }
    }if(!used)dep[x]=-1;
    return used;
}

int main(){
    IN(n),IN(m);s=1,t=n;
    for(ll i=1;i<=m;++i){
        ll u,v,w;IN(u),IN(v),IN(w);
        add(u,v,w*T+1);
    }
    ll maxflow=0;
    while(bfs())maxflow+=dfs(s,inf);
    printf("%lld %lld\n",maxflow/T,maxflow%T);
    return 0;
}

本文标题:【题解】 [USACO4.4]Pollutant Control 网络流 luoguP1344

文章作者:Qiuly

发布时间:2019年02月24日 - 00:00

最后更新:2019年03月29日 - 13:52

原始链接:http://qiulyblog.github.io/2019/02/24/[题解]luoguP1344/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。